package day0510

var ans [][]int
var container []int

func combinationSum(candidates []int, target int) [][]int {
	ans = make([][]int, 0)
	container = make([]int, 0)
	backTrack(0, candidates, target)
	return ans
}

func backTrack(idx int, candidates []int, target int) {
	if target == 0 {
		tmp := make([]int, len(container))
		copy(tmp, container)
		ans = append(ans, tmp)
		return
	}
	for i := idx; i < len(candidates); i++ {
		if target-candidates[i] < 0 {
			continue
		}
		container = append(container, candidates[i])
		backTrack(i, candidates, target-candidates[i])
		container = container[:len(container)-1]
	}
}
